/* /////////////////////////////////////////////////////////////////////////////
 * File:        StringFeature.d
 *
 * Purpose:     文字列の特徴量
 *
 * Created      4th June 2007
 * Updated:     6th June 2007
 *
 * www:         http://
 *
 * Copyright (C) 2007 by Yasunobu Imamura
 *
 * This software is provided 'as-is', without any express or implied warranty.
 * In no event will the authors be held liable for any damages arising from the
 * use of this software.
 *
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute it
 * freely, subject to the following restrictions:
 *
 * 1. The origin of this software must not be misrepresented; you must not claim
 * that you wrote the original software. If you use this software in a product,
 * an acknowledgment in the product documentation would be appreciated but is
 * not required.
 *
 * 2. Altered source versions must be plainly marked as such, and must not be
 * misrepresented as being the original software.
 *
 * 3. This notice may not be removed or altered from any source distribution. 
 *
 * ////////////////////////////////////////////////////////////////////////// */

module gtree.StringFeature;

private import std.stdio;
private import gtree.all;

class StringFeature(C, alias Norm) : ISerializable, IMetrizable, ICloneable
{
	alias StringFeature!(C, Norm) MyType;
	mixin Norm!(C);

	C[] data;
	this()
	{
	}
	this(C[] data2)
	{
		data = data2.dup;
	}
	void serialize(Serializer s)
	{
		s.serialize(&data);
	}
	MyType clone()
	{
		return new MyType(data);
	}
}

template StringEditDistanceNorm(C)
{
	alias int DistanceType;
	DistanceType distance(MyType o)
	{
		C[] a = this.data;
		C[] b = o.data;
		if(b.length < a.length)
		{
			C[] dmy = a;
			a = b;
			b = dmy;
		}

		//これは何がなんでもスタックにメモリを取る必要がある
		scope m = new DistanceType[a.length + 1];

		//mの初期化
		for(int i=0; i<=a.length; ++i)
		{
			m[i] = i;
		}
		//foreach(int i, ref DistanceType mm; m)
		//{
		//	mm = i;
		//}

		DistanceType k;
		for(int j=0; j<b.length; ++j)
		{
			C c = b[j];
			k = j+1;
			for(int i=0; i<a.length; ++i)
			{
				DistanceType k2 = m[i] + (c!=a[i]);
				m[i] = k;

				//aから削除（bに挿入）
				++k;  // int k1 = k + 1; k = k1;

				//置換
				if(k2<k)
					k = k2;

				//bから削除（aに挿入）
				k2 = m[i+1] + 1;
				if(k2<k)
					k = k2;
			}
			m[a.length] = k;
		}

		//writefln(".");
		return k;
	}
}
